import numpy as np
import pandas as pd
from collections import Counter, defaultdict
import string
import plotly.express as px
import plotly.offline as py
from typing import Dict

cyrillic_alphabet = set('абвгдеёжзийклмнопрстуфхцчшщъыьэюя')
ascii_alphabet = set(string.ascii_lowercase)
print(f'cyrillic_alphabet={sorted(list(cyrillic_alphabet))}')
print(f'ascii_alphabet={sorted(list(ascii_alphabet))}')

cyrillic_alphabet=['а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'т', 'у', 'ф', 'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я', 'ё']
ascii_alphabet=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

Вспомогательные функции

def read_file(filename):
    with open(filename, 'r') as fn:
        return fn.read()
    
def clear_text(text, alphabet, add_space=True):
    permitted_chars = alphabet
    if add_space:
        permitted_chars = set(alphabet) | {" "}
    return ''.join(x for x in text.lower() if x in permitted_chars)
    
def count_n_grams(text, n=1):
    counter = Counter()
    for start in range(0, len(text) - n + 1):
        counter.update([text[start : start+n]])
    return counter

def read_corpus(filename, alphabet, n_gram_size=1, add_space=True):
    text = read_file(filename)
    text = clear_text(text, alphabet, add_space)
    return count_n_grams(text, n_gram_size)

def corpus_to_df(corpus):
    df = pd.DataFrame([dict(char=k, count=v) for k,v in corpus.items()])
    total_num = float(sum(corpus.values()))
    df['count'] /= total_num
    return df.sort_values('char')

def generate_samples(filename, alphabet, min_len, max_len, number_of_samples, add_space=True):
    sample = read_file(filename)
    sample = [clear_text(x, alphabet, add_space) for x in sample.split('\n')]
    sample = [x for x in sample if min_len <= len(x) <= max_len]
    return np.random.choice(sample, number_of_samples)

def permutate(sample):
    chars = list(set(sample))
    original_chars = list(set(sample))
    np.random.shuffle(chars)
    permutation = {orig: to for orig, to in zip(original_chars, chars)}
#     for orig, to in zip(original_chars, chars):
#         print(f'replacing {orig} -> {to}')
    return ''.join(permutation[c] for c in sample), permutation

def unpermutate(permutated_text, permutation):
    inversed_index = {v:k for k,v in permutation.items()}
    return ''.join(inversed_index[c] for c in permutated_text)

def freq_to_sorted_list(freq: Dict):
    return sorted([(k,v) for k,v in freq.items()], key=lambda x: -x[-1])

def plot_accuracy(x, y, title, window):
    fig = px.scatter(x=x, y=y, title=title,
                 labels={'x': 'length of sample', 'y': 'accuracy'})
    sums, counts = defaultdict(float), defaultdict(int)
    for xi, yi in zip(x, y):
        x_key = xi // window * window
        sums[x_key] += yi
        counts[x_key] += 1
    mean_x = sorted(sums.keys())
    fig.add_scatter(x=mean_x, y=[sums[xi]/counts[xi] for xi in mean_x], name='mean line', opacity=0.7, )
    return fig

1. Базовый частотный анализ

• подсчитайте частоты букв по корпусам (пунктуацию и капитализацию можно просто опустить, а вот пробелы лучше оставить);
• возьмите какие-нибудь тестовые тексты (нужно взять по меньшей мере 2-3 предложения, иначе вряд ли сработает), зашифруйте их посредством случайной перестановки символов;
• расшифруйте их таким частотным методом.

print(f"Example of cleared text:\n\t{clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)[:400]}")
wap_corpus = read_corpus('WarAndPeace.txt', cyrillic_alphabet)
fig = px.histogram(corpus_to_df(wap_corpus), x='char', y='count', 
                    labels={'count':'char count'}, 
                    title='Chars distribution')

Example of cleared text:
	война и мир  самый известный роман льва николаевича толстого как никакое другое произведение писателя отражает глубину его мироощущения и философииэта книга из разряда вечных потому что она обо всем  о жизни и смерти о любви и чести о мужестве и героизме о славе и подвиге о войне и мирепервый том знакомит с высшим обществом россии  века показаны взаимоотношения между родителями и детьми в семье ро

def try_decode_1gram(sample, corpus):
    sample_freq = count_n_grams(sample, n=1)
    sample_freq = freq_to_sorted_list(sample_freq)
    corpus_freq = freq_to_sorted_list(corpus)
    inverted_index = {}
    for sc, cc in zip(sample_freq, corpus_freq):
        from_c, _ = sc
        to_c, _ = cc
        inverted_index[from_c] = to_c
#         print(f'encoding {from_c} -> {to_c}')
    return ''.join(inverted_index[c] for c in sample)

def char_accuracy(s1, s2):
    total = 0
    equal = 0
    for c1, c2 in zip(s1, s2):
        total += 1
        equal += c1 == c2
    return 100.0 * equal / total

debug_output = False
x, y = [], []
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
                           min_len=100, max_len=1000, number_of_samples=1000)
for sample in samples:
    encoded, permutation = permutate(sample)
    decoded = try_decode_1gram(encoded, wap_corpus)
    acc = char_accuracy(sample, decoded)
    x.append(len(sample))
    y.append(acc)
    if debug_output:
        print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
        print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='One-gram frequency analysis', window=10)
fig.show()

2. Частотный метод с использованием биграмм

bigrams = read_corpus('WarAndPeace.txt', cyrillic_alphabet, n_gram_size=2, add_space=False)
sorted_cyrrilic_abc = sorted(list(cyrillic_alphabet))
bigrams_dist = np.zeros((len(sorted_cyrrilic_abc), len(sorted_cyrrilic_abc)))
for i, a in enumerate(sorted_cyrrilic_abc):
    for j, b in enumerate(sorted_cyrrilic_abc):
        bigrams_dist[i][j] = bigrams.get(a + b, 0.0)
        
print(f'Most common bigrams: {bigrams.most_common(10)}')
px.imshow(
    bigrams_dist,
    labels=dict(x="Second letter", y="First letter", color="Couccurance"),
    x=sorted_cyrrilic_abc,
    y=sorted_cyrrilic_abc,
    title="Bigrams distribution"
)

Most common bigrams: [('то', 8663), ('ст', 6846), ('на', 6585), ('ов', 6487), ('ал', 5857), ('го', 5802), ('он', 5621), ('не', 5581), ('но', 5542), ('ко', 5494)]

most_frequent_bigrams = bigrams.most_common(100)
px.histogram(
    x=[i[0] for i in most_frequent_bigrams], 
    y=[i[1] for i in most_frequent_bigrams],
    labels={'x': 'bigrams', 'y': 'count'},
    title='100 most common bigrams'
)

Поискав в Интеренете, про биграммный поиск пишут, что он просто аналогичен обычному. Тем не менее, у меня не сложилось четкого понимания, как декодировать с помощью биграмм. Очевидно, мы считаем частоту совстречаемости пар символов. Однако, дальше возникает вопрос, что делать.

Например, вот у нас в закодированной последовательности встречается такая комбинация: $$a_{t-1} a_t a_{t+1} a_{t+2}$$ Пусть мы знаем, что среди них $a_t a_{t+1}$ являются самой частой парой, и в соответствии с корпусом, мы им назначаем пару $b_t b_{t+1}$. Дальше возникает вопрос, как действовать. Например, пара $a_{t-1} a_t$ является следующей по частоте встречаемости, но ей соответсвует (по частоте в корпусе), пара $c_{t-1} c_{t}$, при чем $c_t \neq b_t$

Как поступать в таком случае?

В реализованном ниже примере используется следующий подход: мы выбираем наиболее вероятную пару из допустимых. То есть, в данном случае, мы наложим ограничение на выбор $c_{t} \equiv b_{t}$. Это позволяет однозначным образом декодировать. Недостатком является накапливание ошибки: если мы плохо декодировали самую вероятную пару, то дальше алгоритм уже не выправится.

class BiGramDecoder:
    def __init__(self, alphabet, corpus_text):
        self.alphabet = set(alphabet)
        self.corpus_freq = count_n_grams(corpus_text, n=2)
        self.corpus_freq_list = freq_to_sorted_list(self.corpus_freq)
        self.already_processed = {}

    def _decode(self, a, b):
        if a in self.already_processed and b in self.already_processed:
            return self.already_processed[a], self.already_processed[b]
        elif a in self.already_processed:
            best_p = -1.0
            best_c = None
            decoded_a = self.already_processed[a]
            for c in self.alphabet - set(self.already_processed.values()):
                if self.corpus_freq[decoded_a + c] > best_p:
                    best_p = self.corpus_freq[decoded_a + c]
                    best_c = c
            self.already_processed[b] = c
            return decoded_a, c
        elif b in self.already_processed:
            best_p = -1.0
            best_c = None
            decoded_b = self.already_processed[b]
            for c in self.alphabet - set(self.already_processed.values()):
                if self.corpus_freq[c + decoded_b] > best_p:
                    best_p = self.corpus_freq[c + decoded_b]
                    best_c = c
            self.already_processed[a] = c
            return c, decoded_b
        else:
            used = set(self.already_processed.values())
            for seq, _ in self.corpus_freq_list:
                c, d = seq
                if c not in used and d not in used:
                    self.already_processed[a] = c
                    self.already_processed[b] = d
                    return c, d
        
    def __call__(self, sample):
        assert len(self.already_processed) == 0
        sample_freq = freq_to_sorted_list(count_n_grams(sample, n=2))
        letters_in_sample = len(set(sample))
        for seq, cnt in sample_freq:
            a, b = self._decode(seq[0], seq[1])
#             print(f'{seq}[{cnt}] -> {a}{b}')
            if len(self.already_processed) == letters_in_sample:
                break
#         print(self.already_processed)
#         print(sample)
        return ''.join(self.already_processed[c] for c in sample)
    
    def reset(self):
        self.already_processed = {}

debug_output = False
x, y = [], []
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet, add_space=False)
decoder = BiGramDecoder(cyrillic_alphabet, corpus_text)

samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet, add_space=False,
                           min_len=200, max_len=2000, number_of_samples=1000)
for sample in samples:
    encoded, permutation = permutate(sample)
    decoder.reset()
    decoded = decoder(encoded)
    acc = char_accuracy(sample, decoded)
    x.append(len(sample))
    y.append(acc)
    if debug_output:
        print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
        print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='Bi-gram frequency analysis', window=20)
fig.show()

Как видно, результат получился очень неустойчивым, и в среднем хуже, чем для униграмм.